Cloud computing refers to a practice in which a data owner uses remote storage and/or computing resources (e.g., data as a service (DaaS), storage as a service (STaaS)) to store, manage, and process data instead of local storage and/or computing resources. Outsourcing the storage, management, and/or processing of data in this manner may provide a convenient and cost effective solution for limited local storage and/or computing resources. But by storing data to a remote database, a data owner is also relinquishing control over the data to an untrusted cloud service provider and risking exposure of sensitive data to possible misuse. For instance, outsourced data is typically stored in a multi-tenant remote database and may thus comingle with data belonging to other data owners.
To prevent unauthorized access to data stored at the remote database, a data owner may choose to encrypt outsourced data beforehand. However, encrypting data can hinder legitimate attempts to operate on the data because encryption generally obliterates the order that is present in the data. Thus, common database operations that rely on order comparisons (e.g., range queries, sorting, ranking, and/or the like) cannot be performed on the ciphertext of the data. Accordingly, a data owner may be required to decrypt the data before the data owner is able to perform any order-based operation on the data.